package algorithm.sort;

/**
 * @Author liuhaoqi
 * @Date 2020/12/19 15:58
 * @Version 1.0
 * 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {1, 2, 6, 7, 8, 9, 9, 1, 7};
        int[] arrs = insertionSort(arr);
        for (int i : arrs) {
            System.out.println(i);
        }
    }

    public static int[] insertionSort(int[] array) {
        int n = array.length;
        if (n == 0) {
            return array;
        }
        int current ;
        for (int i = 0; i < n - 1; i++) {
            current = array[i + 1];
            int previndex = i;
            //若比较的数组中元素比current当前元素要大 。就把比较的数组中的该元素后移
            while (previndex >= 0 && current < array[previndex]) {
                array[previndex + 1] = array[previndex];
                previndex--;
            }
            //直到遇到比current元素要小或者相等的数组中的元素，此时就把current放到该元素的后面一个
            array[previndex + 1] = current;
        }
        return array;
    }
}
